Move Generation [Static Pieces]
This section will explain generating moves for the following pieces:
- Kings (using a pregenerated tablebase)
- Knights (using a pregenerated tablebase)
- Pawns (on the fly)
Explanation
Static pieces have fixed reach limits that will always remain the same, no matter the position. Pawns cannot move backwards, kings cannot move off of the board - you get the idea.
Because these all have fixed rules, we can generate them all once and store them in a table. Here's an example for all king moves.
Code
fileA = 0x101010101010101
fileH = 0x8080808080808080
def get_king_moves(square: int):
directions = [7, 8, 9, 1]
moves = 0
current = 1 << square
for direction in directions:
moves |= current << direction
moves |= current >> direction
if current & fileA:
moves &= ~fileH
if current & fileH:
moves &= ~fileA
return moves
def create_king_table() -> list[int]:
return [get_king_moves(square) for square in range(64)]
This is simple enough to understand. Let's dive a little deeper.
Explanation
We have a square parameter, say it's 35, then we shift 1 to that amount to create a bitmask like this:
# bb of 1 << 35
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Then we take an empty bitboard (value of 0) then we OR values onto it, which is like pasting bits onto the bitboard.
# current square # direction: 7 # direction: 8 # direction: 9 # direction: 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 1 . . . . . . . . 1 . . . . . . . . 1 . . . . . . . . . . .
. . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . . .
. . . . . . . . . . . . 1 . . . . . . 1 . . . . . . 1 . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Shifting left moves the bit higher up the bitboard and shifting right moves the bit lower down the bitboard. When combining all four of these bitmasks, we get this:
. . . . . . . .
. . . . . . . .
. . 1 1 1 . . .
. . 1 . 1 . . .
. . 1 1 1 . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
However, if the square was 32, this is what the moves would look like:
. . . . . . . .
. . . . . . . 1
1 1 . . . . . 1
. 1 . . . . . 1
1 1 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
The bits overlap to the other side! To counter this, we include two if statements where if the current square is on the A file, we discard any bits from the H file, and vice versa, resulting in this:
# current bits # ~fileH # current & ~fileH
. . . . . . . . 1 1 1 1 1 1 1 . . . . . . . . .
. . . . . . . 1 1 1 1 1 1 1 1 . . . . . . . . .
1 1 . . . . . 1 1 1 1 1 1 1 1 . 1 1 . . . . . .
. 1 . . . . . 1 1 1 1 1 1 1 1 . . 1 . . . . . .
1 1 . . . . . . 1 1 1 1 1 1 1 . 1 1 . . . . . .
. . . . . . . . 1 1 1 1 1 1 1 . . . . . . . . .
. . . . . . . . 1 1 1 1 1 1 1 . . . . . . . . .
. . . . . . . . 1 1 1 1 1 1 1 . . . . . . . . .
We bitwise AND our generated mask against all the bits that are not on the H file, removing all the bits on the H file. We can do a similar thing for the A file with:
if current & fileH:
current &= ~fileA
We then create a list comprehension of all the bitmasks and store it in a list.